#include <iostream>
#include <unordered_set>

using namespace std;

typedef struct {
    int val;
    ListNode* next;
} ListNode;

/**
  * @方法: 快慢指针
  * @时间复杂度: o(n)
  * @空间复杂度: o(1)
  * @评价: 比较好
*/
bool hasCycle1(ListNode* head) {
    ListNode *slow = head;
    ListNode *fast = head;
    while(fast && fast->next && fast->next->next){
        fast = fast->next->next;
        slow = slow->next;
        if(fast == slow){
            return true;
        }
    }
    return false;
}

/**
  * @方法: 哈哈
  * @时间复杂度: o(n)
  * @空间复杂度: o(n)
  * @评价: 注意 unodered_set 的使用
*/
bool hasCycle2(ListNode* head){
    ListNode *p = head;
    unordered_set<ListNode*> visited;
    while(p){
        if(visited.count(p)){
            return true;
        }
        visited.insert(p);
        p = p->next;
    }
    return false;
}

/**
  * @方法: dummy 的使用
  * @时间复杂度: o(n)
  * @空间复杂度: o(1)
  * @评价: 破坏了原链表, 此方法作为学习 dummy 使用
*/
bool hasCycle(ListNode *head){
    ListNode dummy;
    ListNode *p = head;
    ListNode *q;
    while(p && p->next){
        if(p->next == &dummy){
            return true;
        }
        q = p->next;
        p->next = &dummy;
        p = q;
    }
    return false;
}


int main() {
    cout << "hello world" << endl;
    return 0;
}